Presently, there are numerous operating systems (OSs) which are designed for use in various types of computer systems. A high percentage of the operating systems currently in use are vulnerable to corruption, security breaches and other misuse either by intentional or unintentional means. One way of corrupting the execution of a computer is to corrupt the execution stack within the operating system. For example, a skilled hacker can write past the end of an array which was previously declared as an automatic variable in a routine. This form of corruption is commonly known as stack override, buffer overflow, smashing the stack, trashing the stack, mangling the stack and others.
The technique of stack override is a sophisticated technique for attacking and bypassing software security mechanisms of the operating system. Stack override can be described as exploitation of a weakness detected in one or more system utilities so as to gain unlimited access to virtually all areas within the operating system including data, processes or applications that are running on the system. The technique of stack overriding (including how to detect weaknesses in system utilities and how to build an exploit program) is explained in more detail in `Smashing the Stack for Fun and Profit,` Phrack Magazine, Volume 49.
Weaknesses in a system utility, or any other piece of code, are typically caused by careless programming. These weaknesses are surprisingly very common and, as it turns out, very easy to exploit. The mechanism and operation of computer programs that utilize stack override to corrupt and abuse a computer system have been discussed at length in the prior art and especially on public sites on the Internet. Despite extensive discussions on the subject, an acceptable solution to the problem has not been offered.
A high level logical block diagram illustrating a memory map for a process in a typical computer operating system is shown in FIG. 1. Most processes that execute in a computer system are divided into three types of regions within the memory 12 of the computer. The three regions are referred to as text 18, data 16 and stack 14 regions. The size of the text region 18 is in accordance with the program and comprises both processor instructions (code) and read only data. The text region corresponds to the text section of an executable file. In addition, the text region is typically marked as read only and any attempt to write into it results in a segmentation violation. The data region 16 comprises both initialized and uninitialized data and functions to store variables declared in the program. The data region corresponds to the data-bss sections of the executable file.
The stack region 14 is a data structure that is extensively used by the majority of commonly available operating systems. The stack is basically a contiguous block of memory (i.e., a buffer, that is written to and read from in a particular manner). A stack is an abstract data type that has the property that the last item placed on the stack is the first item to be removed. This type of queue is commonly known as last in first out (LIFO) queue. Two key operations that can be performed on stacks include PUSH and POP. A PUSH adds an item to the top of the stack and a POP removes an item from the top of the stack. The bottom of the stack is set to a fixed location while the top of the stack varies as data is pushed onto and popped off of the stack. Depending on the processor implementation, the stack can either grow down towards lower memory addresses or can grow up towards upper memory addresses. Typically, the stack grows down as on Intel, Motorola, SPARC and MIPS processors. In addition, the stack pointer which indicates the current top of the stack may point to the value at the top of the stack or may point to the next available location beyond the top. Typically, the stack pointer indicates the last value written to the top of the stack.
A buffer is a contiguous block of memory in a computer system that contains multiple instances of the same data type. Most of the time, the term buffer is synonymous with the word array. In a typical computer language such as the C programming language, arrays can be declared either static or dynamic. Memory space for static variables are allocated at load time within the data segment. However, dynamic variables are loaded at run time on the stack. Thus, stacks are used to dynamically allocate space for the local variables used in functions, to pass parameters to the function and to return values from the function. A buffer is said to have overflowed when data is written past the edge of the buffer. The terms `stack based buffer overflow` or `stack override` refers to writing data onto the stack beyond the boundaries of a stack memory area previously allocated to a particular variable.
In practice, the stack is utilized in many operating systems as a standard mechanism in making function calls. The stack is comprised of logical stack frames that are pushed when a function is called and popped when a function returns. The stack frame is typically comprised of the parameters of the function, its local variables and the data necessary to recover the previous stack frame, which includes the value of the instruction pointer at the time the function call is made. Stack buffers are utilized in making calls to and returning from functions. In addition, stack buffers are used in the allocation of automatic variables. Automatic variables are variables that are local to the internal function which are released as soon as the function processing terminates. Thus, the return address of the calling function (i.e., the address to which the function should return) and any local variables of the function are located on the stack.
The scope of a local variable is exceeded by attempting to assign a long value to a local variable having a short scope. For example, a local character variable may be declared having a size of 10 characters. The scope of this local variable may be exceeded or overridden by assigning a value 100 characters long to the local variable. Doing this might not only override other local variables of the function, but may also override the return address of a function. If the return address of a function is overwritten on the stack, then when that function terminates and attempts to return, control will pass to the particular address that was written into the location of the return address of the former calling function.
Using this technique of overwriting a shorter variable on the stack with the contents of a longer variable, control can be passed to any arbitrary piece of executable code, and can potentially permit the user to gain access to the entire computer system. However, in order for this technique to work, two requirements must first be met: (1) there must be a way to control the value of the longer length variable used to overwrite the shorter variable, e.g., through an external interface such as command line arguments, environment variables, user input or text configuration files and (2) it must be known how the stack is constructed at the time the shorter variable is overwritten (i.e., overridden, with the value of the longer variable).
In order to override the stack and gain control of the system, the value of the longer length variable (i.e., the overriding variable) is chosen in such a way that the return address used by the system is not arbitrary, but rather is selected to pass control to a section of executable code that effectively grants the user virtually complete control of the computer system. The code that fills the contents of the longer length variable with code to effect control of the computer system (i.e., all permitting code) is termed the exploit program. In addition to placing the code to be executed in the longer length variable, the exploit program functions to detect the weakness in system utilities and to calculate the replacement return address to be overwritten onto the stack. The technique of building an exploit is described in more detail in the publication "Smashing the Stack for Fun and Profit" disclosed above.
Presently, there are hundreds of published exploits to most of the commercial versions of many operating system. A new exploit is published by various groups almost on a weekly basis. Note, however, that the technique of stack override is not applicable to operating systems which do not use the stack as the method of passing control to and returning from functions. Examples of such operating systems include, but are not limited to, IBM MVS, IBM VS1 and IBM VM.
As described above, computer attacks based on the technique of overriding the stack are possible due to a variety of reasons acting in combination. First, careless programming contributes to permitting the stack to be overwritten. Programming mistakes are difficult and time consuming to prevent, thus it can be assumed that for every mistake that is found and corrected, there is another one that goes undetected. Second, the stack itself is used as a mechanism for storing local variables as well as the function call return address and that to alter this fact without altering the essential functionality of the operating system is virtually impossible. Third, the stack is located in a memory segment which is executable in nature, meaning it is possible that data in the stack can be executed as code.
In connection with this third reason, most of the prior art solutions to the stack override problem attempt to make the stack non executable. However, the stack cannot be made non executable as most of the error handling, signal trapping, recovery routines, etc. are pushed onto the stack. Thus, there is no way to make the stack non executable without modifying the essential functionality of the operating system. Even if software applications could be designed to function with an operating system where the stack is non executable, legacy software would not be able to execute on new systems where the stack is no longer executable.